#include <iostream>
#include <stdio.h>

#include <vector>


//先将data[0]与data[1]比较
// 0 1 2
// 0 1 2 3
//插入排序
template<class T>
void insertionsort(T data[], int arrSize)
{
    for(int i = 1, j; i < arrSize; i++){
        T tmp = data[i];
        for(j = i; j > 0&&tmp < data[j-1]; j--)
            data[j] = data[j-1];
        data[j] = tmp;
    }
}

//i-n找出最小，然后与i交换
//选择排序
template<class T>
void selection(T data[], int arrSize)
{
    for(int i = 0,j , min; i < arrSize-1; i++){
        for(j = i+1, min = i; j < arrSize; j++){
            if(data[j] < data[min])
                min = j;
        }
        T tmp = data[min];
        data[min] = data [i];
        data[i] = tmp;
    }
}

//将最小的向前交换
//冒泡
template<class T>
void bubblesort(T data[], int arrSize)
{
    for(int i = 0; i < arrSize-1; i++){
        for(int j = arrSize-1; j>i; j--){
            if(data[j] < data[j-1]){
                T tmp = data[j];
                data[j] = data[j-1];
                data[j-1] = tmp;
            }
        }
    }
}


//梳排序
template<class T>
void combsort(T data[], const int arrSize)
{
    int step = arrSize,j,k;
    while((step = int(step/1.3)) > 1){
        for(j = arrSize-1; j >= step; j--){
            k = j-step;
            if(data[j] < data[k]){
                T tmp = data[j];
                data[j] = data[k];
                data[k] = tmp;
            }
        }
    }


    bool again =true;
    for(int i = 0; i < arrSize-1 && again; i++){
        for(j = arrSize-1, again = false; j > i; --j){
            if(data[j] < data[j-1]){
                T tmp = data[j];
                data[j] = data[j-1];
                data[j-1] = tmp;
            }
        }
    }
}

//希尔排序
template<class T>
void shellSort(T data[], int arrSize)
{
    register int i, j, hCnt, h;
    int increments[20], k;


    for(h = 1, i=0; h< arrSize; i++){
        increments[i] = h;
        h = 3*h + 1;
    }

    for(i--; i >= 0; i--){
        h = increments[i];
            for(j = h; j < arrSize;j++){
                T tmp = data[j];
                k = j;
                while (k-h>=0 && tmp < data[k-h])
                {
                    data[k] = data[k-h];
                    k-=h;
                }
                data[k] = tmp;
                
            }
        // }
    }
}


//堆排序
template<class T>
void swap(T *a ,T *b)
{ 
 T tmp;
 tmp=*a;
 *a=*b;
 *b=tmp;
}
template<class T>
// 递归方式构建大根堆(len是arr的长度，index是第一个非叶子节点的下标)
void adjust(T arr[], int len, int index)
{
    int left = 2*index + 1; // index的左子节点
    int right = 2*index + 2;// index的右子节点
 
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx])     maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx])     maxIdx = right;
 
    if(maxIdx != index)
    {
        swap<T>(&arr[maxIdx], &arr[index]);
        adjust(arr, len, maxIdx);
    }
 
}
 
// 堆排序
template<class T>
void heapSort(T arr[], int size)
{
    // 构建大根堆（从最后一个非叶子节点向上）
    for(int i=size/2 - 1; i >= 0; i--)
    {
        adjust(arr, size, i);
    }
 
    // 调整大根堆
    for(int i = size - 1; i >= 1; i--)
    {
        swap<T>(&arr[0], &arr[i]);           // 将当前最大的放置到数组末尾
        adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
    }
}


//快速排序
template<class T>
int getStandard(T arr[], int i, int j)
{
    T key = arr[i];
    while (i<j)
    {
        /* code */
        while(i < j && arr[j] > key){
            j--;
        }
        if(i < j){
            arr[i] = arr[j];
        }

        while(i < j && arr[i] <= key){
            i++;
        }
    }
    
}


#include <malloc.h>
#include <stdlib.h>
void mergesort(int A[],int n)  //合并排序的递归主体
{
    void merge(int A[], int L[], int R[], int l, int r);  //声明merge函数
    if(n>1)    //多于一个元素才需要排序
    {
        int mid=n/2;
        int *left=(int*)malloc(sizeof(int)*mid);
        int *right=(int*)malloc(sizeof(int)*(n-mid));
        for(int i=0;i<mid;i++)
            left[i]=A[i];       //建立临时数组存储左半部分序列
        for(int j=mid;j<n;j++)
            right[j-mid]=A[j];  //建立临时数组存储右半部分序列
 
        mergesort(left,mid);    //调用自身对左半部分进行合并排序
        mergesort(right,n-mid); //调用自身对右半部分进行合并排序
        merge(A,left,right,mid,n-mid);   //两个有序序列的合并操作，封装为函数
        free(left);
        free(right);
    }
}
 
void merge(int A[],int L[],int R[],int l,int r)  //两个有序序列L、R合并为A，l,r分别为L,R的长度
{
    int i=0,j=0,k=0;
    while(i<l&&j<r)  //两个子序列首元素做比较，小者取出置入父序列
    {
        if(L[i]<=R[j])
            A[k++]=L[i++];
        else
            A[k++]=R[j++];
    }
    while(i<l)       //将左半部分剩余元素置入父序列
    {
        A[k++]=L[i++];
    }
    while(j<r)       //将右半部分剩余元素置入父序列
    {
        A[k++]=R[j++];
    }
}

int main(int argv, char**argc)
{
    printf("************  test hello zc!!!   **************\n");
    /* add test code! */
    
    int array[11] = {2,1,4,3,11,6,5,7,8,10,15};
    // shellSort<int>( array, 11);  //希尔排序
    // insertionsort<int>( array, 11);  //直接插入排序
    // selection<int>( array, 11);   //直接选择排序
    // bubblesort<int>( array, 11);  //冒泡排序
    // combsort<int>(array,11);      
    // heapSort<int>(array,11);  //堆排序
    mergesort(array,11);   //归并排序

    for(auto it: array)
    {
        std::cout<<it<<std::endl;
    }
    return 0;
}
